The present invention relates to authentication and validation of items such as currency, identification cards, and documents.
Various forms of cryptography are commonly applied to electronic communications such as e-mail, cellular communications, and secure Internet transactions. In xe2x80x9cpublic keyxe2x80x9d cryptography systems, each of the persons exchanging information receives a pair of keys: the public key and the private key. Each person""s public key is published while the private key is kept secret. Messages are encrypted using the intended recipient""s public key and can only be decrypted using his private key. As a result, the need for sender and receiver to share secret informationxe2x80x94i.e., keysxe2x80x94via some secure channel is eliminated, since all communications involve only public keys. Private keys need not be transmitted or shared.
Public-key cryptography relies extensively on xe2x80x9cone-wayxe2x80x9d functions and xe2x80x9ctrapdoor one-wayxe2x80x9d functions. A one-way function is significantly easier to compute in one direction (the forward direction) than in the opposite direction (the inverse direction). It might be possible, for example, to compute the forward function in polynomial time whereas an algorithm to compute the inverse function runs in exponential time. A trapdoor one-way function is a one-way function whose inverse direction is easy to compute given a certain piece of information (i.e., the trapdoor, which may be, for example, a prime factor) but difficult otherwise.
State-of-the-art authentication and digital-signature schemes also rely on xe2x80x9cone-way hashxe2x80x9d functions. A hash function takes a variable-size input, called a xe2x80x9cpre-image,xe2x80x9d and reduces it to a fixed-size output called the xe2x80x9chash value.xe2x80x9d Hash functions are known by many names, among them compression functions, fingerprints, cryptographic checksums, and manipulation-detection codes. For one-way hash functions, it is easy to compute the hash value from the pre-image, but very difficult to compute the pre-image given the hash value.
The benefits of crytography stem from its high degree of reliability and low cost, since messages are readily encrypted and an encrypted message is as easily communicated as its unsecured counterpart. These benefits, however, presume that the message is realized as an electronic artifact or signal whose only value lies in the contents of what is encrypted. Information associated with physical objects, by contrast, is less amenable to protection by encryption since typically it is the object, and not the information, that has value. For example, even elaborate signatures intended to identify and authenticate documents or currency can be defeated by accurate copying.
An intermediate case is the so-called xe2x80x9csmart cardxe2x80x9dxe2x80x94a credit card-sized device with an embedded chip used to identify the card and, depending on the application, containing additional information such as a monetary amount to which the cardholder is entitled. The digital information in a smart card is not amenable to easy duplication, as in the case of currency, yet because the information is contained within a physical medium, it may still be accessible toxe2x80x94and forged byxe2x80x94an unlawful possessor of the card. Talented thieves have successfully gained access to the value stored on cards by means of reverse engineering, fault analysis, and side-channel attacks such as power and timing analysis.
One proposed approach toward preventing forgery, applicable to ordinary items as well as to smart cards, is to utilize unique, hard-to-forge features intrinsic to the item itself. For example, U.S. Pat. Nos. 5,521,984, 4,677,435, and 5,325,167 rely on the fine features of an item""s texture to generate a unique identifier associated with the item. The identifier is easy to generate but difficult to forge because it stems from physical attributes that are both highly numerous and random in nature.
Despite the appeal of this approach, the use of texture as contemplated in the prior art poses limitations. Surface texture is a two-dimensional artifice that can, with sufficiently accurate copying technology, be reproduced. Moreover, texture necessarily exposed to the environment and can change over time, particularly in the case of items (such as paper currency) that are routinely handled. While this does not necessarily facilitate forgery, it can impede validation, since the features used to compute the identifier may disappear or undergo change to an extent that destroys the physical key. Texture is also vulnerable to deliberate tampering, which can defeat identification altogether.
In accordance with the present invention, three-dimensional characteristics (rather than merely surface texture) of a complex physical structure are used in a mathematical function to identify the structure. In effect, the characteristics reperesent the basis of a xe2x80x9cphysical one-way hash functionxe2x80x9dxe2x80x94i.e., a fixed-size string of digits that is obtained by probing a complex three-dimensional structure. The characteristics are read using a non-contact probe, and preferably without the need for precise registration. The term xe2x80x9ccomplexxe2x80x9d is used herein to connote a structure that is easy to fabricate and to probe, but extremely difficult to accurately refabricate. The complexity may arise, for example, from inhomogeneity within the structure, from randomness or disorder, or from ordered but extremely complex structural featuers. The structure may be minuscule or large, depending on the application.
The features that form the basis of the identification may occur naturally in the item to be identified, or may instead be generated. Large physical structures with fine features are straightforwardly constructed yet difficult to duplicate accurately, owing to the random nature and density of the features. For example, voids or bubbles may be introduced into a polymeric matrix as it cures, resulting in a three-dimensional network of features. In this case, the features may be examined three-dimensionally using a tomographic technique, which reveals the pattern of voids on a slice-by-slice basis. More simply, coherent light may be directed through the structure and received optically; the resulting pattern (xe2x80x9cspecklexe2x80x9d), although viewed as a two-dimensional image, nonetheless contains substantial information about the three-dimensional pattern.
Other three-dimensional structures from which identifying information may be extracted include fused sand and multiphase materials (e.g., granular particles permanently suspended in a polymeric matrix, or alloys with different chemical and/or structural compositions), the distribution of the different phases providing the complexity. Complexity can also arise from differences in orientation and/or symmetry (e.g., in polycrystalline materials), from structural defects (e.g., in grown crystals), or from irregularities in interfaces between different materials (or phases of the same material). The authenticating three-dimensional structure may be inherent within an item, or may instead be physically introduced into or associated with an item to facilitate its authentication.
The level of detail used for identification need only be as fine as is necessary to reliably distinguish a particular structure from similar ones; or in the framework of the invention, the identifier derived from the structure need only be large enough (i.e., contain a sufficient number of bits) to be unique. By avoiding excessive structural characterization, the invention permits examinations to occur without precise registration. For example, a hash function may act on data derived from the physical structure to produce a hashed key. In principle, it is impossible to go backwards from a hashed key to the data derived from the physical structure. The hash function operates at a level of feature resolution appropriate to the desired degree of uniqueness. Generally, the identifier generated from the inhomogeneous structure can be used in either symmetric or asymmetric cryptography techniques.